#include<cstdio>
#include<cstring>
const int maxn=100001;
const int MAXINT=2100000000;
struct node
{
	int no,v,l,r,p;
}tree[maxn*10];
int z=0,root=-1;
void insert()
{
	int x=root;
	int y=-1;
	while(x!=-1)
	{
		y=x;
		if(tree[z].v<tree[x].v)
			x=tree[x].l;
		else
			x=tree[x].r;
	}
	tree[z].p=y;
	if(y==-1)
		root=z;
	else if(tree[z].v<tree[y].v)tree[y].l=z;
		 else tree[y].r=z;
}
int findmax(int &root)
{
	if(root==-1)return 0;
	int u=root;
	while(tree[u].r!=-1)
		u=tree[u].r;
	if(u!=root)
	{
		tree[tree[u].p].r=tree[u].l;
		if(tree[u].l!=-1)tree[tree[u].l].p=tree[u].p;
	}
	else root=tree[u].l;
	return tree[u].no;
}
int findmin(int &root)
{
	if(root==-1)return 0;
	int u=root;
	while(tree[u].l!=-1)
		u=tree[u].l;
	if(u!=root)
	{
		tree[tree[u].p].l=tree[u].r;
		if(tree[u].r!=-1)tree[tree[u].r].p=tree[u].p;
	}
	else root=tree[u].r;
	return tree[u].no;
}


int main()
{
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	
	int op;
	while(scanf("%d",&op),op!=0)
	{
		if(op==1)
		{
			int no,val;
			scanf("%d%d",&no,&val);
			z++;
			tree[z].no=no;
			tree[z].v=val;
			tree[z].l=tree[z].r=-1;
			insert();
		}
		if(op==2)printf("%d\n",findmax(root));
		if(op==3)printf("%d\n",findmin(root));
	}
	return 0;
}
		
	
	
